import java.util.*;
public class test {
    // leetcode 2418.按身高排序
    public String[] sortPeople(String[] names, int[] heights) {
        HashMap<Integer,ArrayList<String>> map = new HashMap<>();
        int n = heights.length;
        for(int i = 0;i < n;i++){
            int temp = heights[i];
            ArrayList<String> list = map.getOrDefault(temp,new ArrayList<String>());
            list.add(names[i]);
            map.put(temp,list);
        }
        Arrays.sort(heights);
        n = map.size();
        int index = 0;
        String[] arr = new String[n];
        for(int i = n - 1;i >= 0;i--){
            int temp = heights[i];
            for(String s : map.get(temp)){
                arr[index++] = s;
            }
        }
        return arr;
    }
    // leetcode 870.优势洗牌
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums1.length;
        HashMap<Integer,ArrayList<Integer>> map = new HashMap<>();
        // [1,10,4,10,11] -> [1,2,3,4,5]
        // [1,4,10,10,11] -> [1,3,2,4,5]
        for(int i = 0;i < n;i++){
            int temp = nums2[i];
            // 根据nums2的值,对下标进行排序,首先创建键值对
            ArrayList<Integer> list = map.getOrDefault(temp,new ArrayList<Integer>());
            list.add(i);
            map.put(temp,list);
        }
        // 8  12 24 32
        // 11 13 25 32
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int[] arr = new int[n];
        Arrays.fill(arr,-1);
        int left = 0;
        int right = n - 1;
        for(int i = 0;i < n;i++){
            int temp1 = nums1[i];
            int temp2 = nums2[left];
            int index = 0;
            // 打不过,直接去后面干掉最大的
            if(temp1 <= temp2){
                // 可能存在相同数,存储的为(下标列表)
                for(int a : map.get(nums2[right])){
                    // 代表已经存放过
                    if(arr[a] != -1) continue;
                    arr[a] = temp1;
                    break;
                }
                right--;
                // 打得过,直接干掉
            }else {
                for(int a : map.get(nums2[left])){
                    // 代表已经存放过
                    if(arr[a] != -1) continue;
                    arr[a] = temp1;
                    break;
                }
                left++;
            }
        }
        return arr;
    }
    // leetcode 455.分发饼干
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int leng = g.length;
        int lens = s.length;
        int i = 0;
        int j = 0;
        while(i < leng && j < lens){
            // 当前饼干不够这个孩子吃
            if(s[j] < g[i]){
                j++;
                continue;
            }else {
                j++;
                i++;
            }
        }
        return i;
    }
}
